package problemLCR114;

import java.util.*;

//LCR11.火星字典
//https://leetcode.cn/problems/Jf1JuT/

class Solution {
    HashMap<Character, Integer> in;
    HashMap<Character, Set<Character>> map;
    boolean check;

    public String alienOrder(String[] words) {
        in = new HashMap<>();
        map = new HashMap<>();
        int n = words.length;
        check = false;

        //初始化入度表
        for(String str : words) {
            for(char ch : str.toCharArray()) {
                in.put(ch, 0);
            }
        }

        for(int i = 0; i<n; i++) {
            for(int j = i+1; j<n; j++) {
                add(words[i], words[j]);
                if(check) return "";
            }
        }

        System.out.println(in);
        System.out.println(map);

        Queue<Character> queue = new LinkedList<>();
        for(Character ch : in.keySet()) {
            if(in.get(ch) == 0) queue.add(ch);
        }

        StringBuffer ret = new StringBuffer();
        while(!queue.isEmpty()) {
            Character t = queue.poll();
            ret.append(t);
            Set<Character> set = map.getOrDefault(t, new HashSet<>());
            for(Character ch : set) {
                in.put(ch, in.get(ch)-1);
                if(in.get(ch) == 0) {
                    queue.add(ch);
                }
            }
        }

        for(Character ch : in.keySet()) {
            if(in.get(ch) != 0) return "";
        }
        return ret.toString();
    }

    public void add(String s1, String s2) {
        int len = Math.min(s1.length(), s2.length());
        int i = 0;
        while(i < len && s1.charAt(i) == s2.charAt(i)) {
            i++;
        }
        
        if(i == len && s1.length() > s2.length()) {
            check = true;
            return;
        }
        if(i < len) {
            char a = s1.charAt(i), b = s2.charAt(i); //a->b
            if(!map.containsKey(a)) map.put(a, new HashSet<>());
            if(!map.get(a).contains(b)) in.put(b, in.getOrDefault(b, 0) + 1);
            map.get(a).add(b);
        }
    }
}